package data_structures_and_algorithms.other;


import java.util.Arrays;

/**
 * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：6
 * 示例 2：
 *
 * 输入：nums = [1,2,3,4]
 * 输出：24
 * 示例 3：
 *
 * 输入：nums = [-1,-2,-3]
 * 输出：-6
 *  
 *
 * 提示：
 *
 * 3 <= nums.length <= 104
 * -1000 <= nums[i] <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-product-of-three-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _628_threeNumMaximumProduct_in_array {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        int product = new _628_threeNumMaximumProduct_in_array().maximumProduct(nums);
        System.out.println(product);
    }

    public int maximumProduct(int[] nums) {
        return maximumProductSort(nums);
    }

    public int maximumProductSort(int[] nums){
        Arrays.sort(nums);
        int length = nums.length;

        return Math.max(nums[length - 1]*nums[length - 2]*nums[length - 3], nums[0]*nums[1]*nums[length - 1]);
    }

    public int maximumProductLineScan(int[] nums){
        // 定义最大的三个数 和 最小的三个数
        int max1 = nums[0], max2 = max1, max3 = max1, min1 = nums[0], min2 = min1;

        for (int i = 1; i < nums.length; i++) {
            // 处理大数
            if (nums[i] > max1){
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            }else if (nums[i] > max2){
                max3 = max2;
                max2 = nums[i];
            }else if (nums[i] > max3){
                max3 = nums[i];
            }
            // 处理小数
            if (nums[i] < min1){
                min2 = min1;
                min1 = nums[i];
            }else if (nums[i] < min2){
                min2 = nums[i];
            }
        }

        return Math.max(max1 * max2 * max3, min1 * min2);
    }

}
